Biologia obliczeniowa

Limit pamięci: 128 MB

Bajtazar pracuje w Bajtockim Centrum Biologii Obliczeniowej. Właśnie dostał do analizy długą sekwencję złożoną z genomów. Jego zadaniem jest znalezienie często powtarzających się cyklicznych fragmentów tej sekwencji.

Sekwencję Bajtazara można reprezentować jako słowo złożone z wielkich liter alfabetu angielskiego. Cyklicznym fragmentem słowa nazywamy takie słowo , że wszystkie obroty cykliczne¹ słowa są podsłowami słowa .

Bajtazara interesują cykliczne fragmenty słowa o ustalonej długości . Dla danego cyklicznego fragmentu słowa , definiujemy liczbę cyklicznych wystąpień w jako łączną liczbę wystąpień wszystkich różnych obrotów cyklicznych słowa w słowie . Bajtazar chciałby znaleźć w słowie cykliczny fragment długości , dla którego liczba cyklicznych wystąpień jest jak największa. Napisz program, który pomoże mu w tym zadaniu.

Wejście

W pierwszym wierszu wejścia znajdują się dwie liczby całkowite oraz (, ), oznaczające długość sekwencji genomów oraz liczbę przypadków testowych do rozważenia. W drugim wierszu znajduje się -literowe słowo złożone z liter 'A''Z' stanowiące reprezentację sekwencji. Dalej następuje wierszy, z których -ty zawiera jedną liczbę całkowitą (), oznaczającą rozważaną długość cyklicznych fragmentów sekwencji.

Wyjście

Twój program powinien wypisać wierszy. Każdy z tych wierszy powinien zawierać jedną liczbę całkowitą, oznaczającą maksymalną liczbę cyklicznych wystąpień -literowego cyklicznego fragmentu słowa .

Przykład

Dla danych wejściowych:

16 2
AABAABACDABAABAA
6
3

poprawną odpowiedzią jest:

4
10

Wyjaśnienie do przykładu: Cykliczny fragment AABAAB występuje w podanym słowie 4 razy: raz jako AABAAB, dwa razy jako ABAABA i raz jako BAABAA. Cykliczny fragment AAB występuje w tym słowie 10 razy.

Autor zadania: Jakub Radoszewski.

1. Obrotem cyklicznym słowa nazywamy słowo powstałe przez (potencjalnie wielokrotne) przeniesienie ostatniej litery słowa na początek. Przykładowo, wszystkimi obrotami cyklicznymi słowa ABAABA są: ABAABA, BAABAA oraz AABAAB. Słowo nazywamy podsłowem słowa , jeśli występuje w jako spójny kawałek.